package com.community.process._1010.common.utils.tree;

import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * 树形结构工具类
 *
 * @author meilin.huang
 * @version 1.0
 * @date 2019-08-24 1:57 下午
 */
public class TreeUtils {

    /**
     * 根据所有树节点列表，生成含有所有树形结构的列表
     *
     * @param nodes 树形节点列表
     * @param <T>   节点类型
     * @return 树形结构列表
     */
    public static <T extends TreeNode> List<T> generateTrees(List<T> nodes) {
        if (CollectionUtils.isEmpty(nodes)) return nodes;
        List<T> roots = new ArrayList<>();
        List<T> nonRoots = new ArrayList<>();
        for (T node : nodes) {
            if (node.root()) {
                roots.add(node);
            } else {
                nonRoots.add(node);
            }
        }
        roots.forEach(r -> setChildren(r, nonRoots));
        return roots;
    }

    /**
     * 从所有节点列表中查找并设置parent的所有子节点
     *
     * @param parent 父节点
     * @param nodes  所有树节点列表
     */
    @SuppressWarnings("all")
    private static <T extends TreeNode> void setChildren(T parent, List<T> nodes) {
        List<T> children = new ArrayList<>();
        Object parentId = parent.id();
        for (Iterator<T> ite = nodes.iterator(); ite.hasNext(); ) {
            T node = ite.next();
            if (Objects.equals(node.parentId(), parentId)) {
                children.add(node);
                // 从所有节点列表中删除该节点，以免后续重复遍历该节点
                ite.remove();
            }
        }
        // 如果孩子为空，则直接返回,否则继续递归设置孩子的孩子
        if (children.isEmpty()) {
            return;
        }
        parent.setChildren(children);
        children.forEach(m -> {
            // 递归设置子节点
            setChildren(m, nodes);
        });
    }

    /**
     * 根据子节点获取父节点
     * @param childrenNode
     * @param nodes
     * @return
     * @param <T>
     */
    public static  <T extends TreeNode> T getParentLeafstalk(T childrenNode, List<T> nodes) {
        if (childrenNode == null) {
            return null;
        }
        if (childrenNode.root()) {
            return childrenNode;
        }
        T tblCategory = nodes.stream().filter(
                node -> Objects.equals(node.id(), childrenNode.parentId())
        ).findFirst().orElse(null);
        if (tblCategory == null) {
            return childrenNode;
        }
        List<T> ts = Collections.singletonList(childrenNode);
        tblCategory.setChildren(ts);
        return getParentLeafstalk(tblCategory,nodes);
    }

    /**
     * 获取指定树节点下的所有叶子节点
     *
     * @param parent 父节点
     * @param <T>    实际节点类型
     * @return 叶子节点
     */
    public static <T extends TreeNode> List<T> getLeafstalk(T parent) {
        List<T> leafstalk = new ArrayList<>();
        fillLeaf(parent, leafstalk);
        return leafstalk;
    }

    /**
     * 将parent的所有叶子节点填充至leafstalk列表中
     *
     * @param parent 父节点
     * @param leafs  叶子节点列表
     * @param <T>    实际节点类型
     */
    @SuppressWarnings("all")
    public static <T extends TreeNode> void fillLeaf(T parent, List<T> leafstalk) {
        List<T> children = parent.getChildren();
        // 如果节点没有子节点则说明为叶子节点
        if (CollectionUtils.isEmpty(children)) {
            leafstalk.add(parent);
            return;
        }
        // 递归调用子节点，查找叶子节点
        for (T child : children) {
            fillLeaf(child, leafstalk);
        }
    }
}